package com.jiang.daily.Q2364;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/04/18 15:46
 */
class Solution {
//    public long countBadPairs(int[] nums) {
//        // j - i != nums[j] - nums[i] => nums[j] - j != nums[i] - i
//        int len = nums.length;
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++)  {
//            // 存储 nums[i] - i 的个数
//            map.put(nums[i] - i, map.getOrDefault(nums[i] - i, 0) + 1);
//        }
//        long res = 0;
//        for (Integer value : map.values()) {
//            // 当前key与其它的key组合的个数  (len - value)表示剩余的个数 value表示当前key的个数
//            res += 1L * value * (len - value);
//            len -= value;
//        }
//        return res;
//    }

    public long countBadPairs(int[] nums) {
        int n = nums.length;
        // 算出所有可能的组合数
        long ans = (long) n * (n - 1) / 2;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i] - i;
            int c = cnt.getOrDefault(x, 0);
            // 减去重复的
            ans -= c;
            cnt.put(x, c + 1);
        }
        return ans;
    }
}
